package main

import "fmt"

func main() {
	nums := []int{3, 4, 8, 8, 8}
	fsort(nums)
	fmt.Println(nums)
}

//快排
func fsort(input []int) {
	if len(input) <= 1 {
		return
	}
	mid := input[0]
	left := 1
	right := len(input) - 1
	//left和right的定义，left左边的都比mid小，right右边的都是大于等于mid,所以最终left会等于right+1
	for left <= right {
		for ; left <= right && mid > input[left]; left++ {
		} //exit:left == right; input[left] >= mid //此处的left <= right 等于符号一定要带上，
		//因为= 符合最外层for循环的条件，如果不带等号，内层的三个判断又不满足，会死循环。而为什么内层的两个for循环都要带上等号，因为不知道left == right时候的那个数字是大于mid还是小于等于mid，如果
		for ; left <= right && mid <= input[right]; right-- {
		} // exit left == right; input[right] < mid
		if left < right {
			//经过上面两次for循环，不可能出现left == right的情况，所以一定是left < right || left > right
			input[left], input[right] = input[right], input[left]
			left++
			right--
		}
	}
	input[right], input[0] = input[0], input[right]
	fsort(input[:right])
	fsort(input[left:])
}
